The key to finding a cycle in a DFS is identifying a "back edge"—an edge that leads to an already visited node that isn't the immediate parent.

  • A cycle is a path in the graph that starts and ends at the same vertex, forming a loop.
  • During a DFS traversal, when we move from node `u` to `v`, `u` becomes the parent of `v`. This helps us build the DFS tree.
  • As DFS explores from a node `u`, it checks each neighbor `w`. If `w` is already visited, we have found a potential back edge.
  • A cycle is confirmed if we find a visited neighbor `w` that is not the parent of `u`. This means we've found an alternative path back to an ancestor in the DFS tree, closing a loop.